#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct node {
  ElemType data;
  struct node *next, *prev;
} Node;

// 初始化双向链表
Node *initList() {
  Node *head = (Node *)malloc(sizeof(Node));
  head->data = 0;
  head->next = NULL;
  head->prev = NULL;
  return head;
}

// 头插法
int insertHead(Node *L, ElemType e) {
  Node *p = (Node *)malloc(sizeof(Node));
  p->data = e;
  p->prev = L;
  p->next = L->next;
  if (L->next != NULL) {
    L->next->prev = p;
  }
  L->next = p;
  return 1;
}

// 尾插法
Node *insertTail(Node *tail, ElemType e) {
  Node *p = (Node *)malloc(sizeof(Node));
  p->data = e;
  p->prev = tail;
  p->next = NULL;
  tail->next = p; // 旧尾节点的 next 指向新节点
  return p;       // 返回新节点，作为新的尾节点
}

// 找到尾节点
Node *get_tail(Node *L) {
  Node *p = L;
  while (p->next != NULL) {
    p = p->next;
  }
  return p;
}

// 在指定位置插入节点
int insertNode(Node *L, int pos, ElemType e) {
  Node *p = L;
  int i = 0;
  while (i < pos - 1) {
    p = p->next;
    i++;
    if (p == NULL) {
      return 0;
    }
  }

  Node *q = (Node *)malloc(sizeof(Node));
  q->data = e;
  q->prev = p;
  q->next = p->next;
  p->next->prev = q;
  p->next = q;
  return 1;
}

// 链表遍历
void listNode(Node *L) {
  Node *p = L->next; // 从头节点的 next 开始遍历
  while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
  }
  printf("\n");
}

// 删除指定位置节点
int deleteNode(Node *L, int pos) {
  Node *p = L;
  int i = 0;
  while (i < pos - 1) {
    i++;
    p = p->next;
    if (p == NULL) {
      return 0;
    }
  }
  Node *q = p->next;
  p->next = q->next;
  q->next->prev = p;
  free(q);
  return 1;
}

int main() {
  Node *list = initList();
  // 头插
  insertHead(list, 10);
  insertHead(list, 20);
  insertHead(list, 30);
  listNode(list);
  // 尾插
  Node *tail = get_tail(list);
  tail = insertTail(tail, 10);
  tail = insertTail(tail, 20);
  tail = insertTail(tail, 30);
  listNode(list);
  // 在第二个位置添加数据40
  insertNode(list, 2, 40);
  listNode(list);
  // 删除第二个位置的数据
  deleteNode(list, 2);
  listNode(list);
}